카드 뭉치

📔 문제 설명

코니는 영어 단어가 적힌 카드 뭉치 2개를 선물로 받았습니다. 코니는 다음과 같은 규칙으로 카드에 적힌 단어들을 사용해 원하는 순서의 단어 배열을 만들 수 있는지 알고 싶습니다.

원하는 카드 뭉치에서 카드를 순서대로 한 장씩 사용합니다.
한 번 사용한 카드는 다시 사용할 수 없습니다.
카드를 사용하지 않고 다음 카드로 넘어갈 수 없습니다.
기존에 주어진 카드 뭉치의 단어 순서는 바꿀 수 없습니다.

예를 들어 첫 번째 카드 뭉치에 ["i", "drink", "water"], 두 번째 카드 뭉치에 ["want", "to"]가 적혀 있을때 ["i","want","to","drink","water"] 순서의 단어 배열을 만들려고합니다. 첫 번째 카드 뭉치에서 "i"를 사용한 후 두 번째 카드 뭉치에서 "want"와 "to"를 사용하고 첫 번째 카드 뭉치에 "drink"와 "water"를 차례대로 사용하면 원하는 순서의 단어 배열을 만들 수 있습니다. 문자열로 이루어진 배열 cards1, cards2와 원하는 단어 배열 goal이 매개변수로 주어질 때 card1s과 cards2에 적힌 단어들로 goal을 만들 수 있다면 "Yes"를, 만들 수 없다면 "No"를 반환하는 solution()함수를 완성하세요

📓 제약 조건

1 <= cards1의 길이, cards2의 길이 <= 10
1 <= cards1 [i]의 길이, cards2[i]의 길이 <= 10
cards1과 cards2에는 서로 다른 단어만 있음
2<=goal의 길이 <= cards1의 길이 + cards2의 길이
1 <= goal[i]의 길이 <= 10
goal의 원소는 cards1과 cards2의 원소들로만 이루어져 있음
cards1, cards2,goal의 문자열들은 모두 알파벳 소문자로만 이루어져 있음

📓 입출력의 예

❗ 1번째

문제는 일단 card1과 card2둘다 앞에서 사용해야하고 순서를 바꿀수없다는 점에서 큐를 사용해서 문제를 풀어야할거같다는 생각을 했다.

일단 먼저 큐에 대한 기능을 하는 역할을 하나 만들어두고 사용해보자

자바스크립트에는 shift 메소드가 있지만 이건 실제로 $O(n)$으로 동작한다 그렇기에 이렇게 클래스를 작성하여 $O(1)$로 동작하게 만들어줘야 큐 자료구조를 구현할수있다

✅ 실행 코드

class Queue {
  items = [];
  front = 0;
  rear = 0;

  constructor(array) {
    this.items = array;
    this.rear = array.length;
  }

  push(item) {
    this.items.push(item);
    this.rear++;
  }

  pop() {
    return this.items[this.front++];
  }

  first() {
    return this.items[this.front];
  }

  isEmpty() {
    return this.front === this.rear;
  }
}

function solution(cards1, cards2, goal) {
  cards1 = new Queue(cards1);
  cards2 = new Queue(cards2);
  goal = new Queue(goal);

  while (!goal.isEmpty()) {
    if (!cards1.isEmpty() && cards1.first() === goal.first()) {
      cards1.pop();
      goal.pop();
    } else if (!cards2.isEmpty() && cards2.first() === goal.first()) {
      cards2.pop();
      goal.pop();
    } else {
      break;
    }
  }

  if (goal.isEmpty()) {
    return "Yes";
  } else {
    return "No";
  }
}

📚 문제 느낀점

아래의 구현부보다 클래스를 구현하는게 훨씬 더 헷갈렸다 뭔가 자바스크립트로 큐 문제를 구현할때 항상 shift를 썻었는데 이런식으로 해보는건 처음이라 되게 신선했다 앞으로도 이렇게 문제를 풀어봐야겠다

© 문제 출처

https://school.programmers.co.kr/learn/courses/30/lessons/159994